//魔术索引。 在数组A[0...n-1]中，有所谓的魔术索引，满足条件A[i] = i。给定一个有序整数数组，编写一种方法找出魔术索引，若有的话，在数组A中找
//出一个魔术索引，如果没有，则返回-1。若有多个魔术索引，返回索引值最小的一个。 
//
// 示例 1： 
//
// 
// 输入：nums = [0, 2, 3, 4, 5]
// 输出：0
// 说明：0下标的元素为0
// 
//
// 示例 2： 
//
// 
// 输入：nums = [1, 1, 1]
// 输出：1
// 
//
// 说明： 
//
// 
// nums长度在[1, 1000000]之间 
// 此题为原书中的 Follow-up，即数组中可能包含重复元素的版本 
// 
//
// Related Topics 数组 二分查找 👍 136 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-07-17 00:10:35
 * @description 面试题 08.03.魔术索引
 */
public class MagicIndexLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 MagicIndexLcci fun=new MagicIndexLcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	public int findMagicIndex(int[] nums) {
		return helper(nums, 0, nums.length - 1);
	}
	//因为题目不是严格递增的，可能存在重复元素，所以需要在左右两部分都查找。
	private int helper(int[] nums, int left, int right) {
		if (left > right) {
			return -1;
		}
		int mid = left + (right - left) / 2;
		if (nums[mid] == mid) {
			// 找到魔术索引，但继续在左侧查找更小的
			int leftRes = helper(nums, left, mid - 1);
			return leftRes != -1 ? leftRes : mid;
		}
		// 必须检查左右两部分，因为数组可能不是严格递增
		int leftRes = helper(nums, left, mid - 1);
		if (leftRes != -1) {
			return leftRes;
		}
		return helper(nums, mid + 1, right);
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
